class Solution:
    def partition(self, s: str):
        if s is None or len(s) == 0:
            return []
        dp = [[] for _ in range(len(s) + 1)]
        for i in range(len(s)):
            if self.isPalindrome(s[:i + 1]):
                dp[i + 1].append([s[:i + 1]])
            for j in range(1, i + 1):
                if self.isPalindrome(s[j:i + 1]):
                    for word in dp[j]:
                        newWord = word.copy()
                        newWord.append(s[j:i + 1])
                        dp[i + 1].append(newWord)
        return dp[-1]

    def isPalindrome(self, s: str):
        if len(s) <= 1:
            return True
        l = len(s)
        for i in range(len(s)//2):
            if s[i] != s[l-i-1]:
                return False
        return True

if __name__ == '__main__':
    so = Solution()
    s ="aab"
    re = so.partition(s)
    print(re)